9608. Такси

Ивана и Сергея пригласили к участию в областной олимпиаде по информатике. Поскольку они проживают в разных населенных пунктах, Иван предложил воспользоваться службой такси, чтобы добраться до места проведения олимпиады.

Такси выезжает из пункта А, где проживает Иван, и направляется в пункт В, забирая Сергея, и дальше едет к месту проведения олимпиады (в пункт С).

Зная длины дорог между населенными пунктами области и стоимость проезда одного километра на такси, посчитайте на сколько больше денег потратил на поездку Иван, заезжая за Сергеем, чем следуя сразу к месту проведения олимпиады.

Известно, что такси всегда выбирает самый короткий из существующих маршрутов.

Вход. В первой строке записано пять чисел – четыре целых и одно действительное:

· n – количество населенных пунктов,

· A – населенный пункт, где проживает Иван,

· B – населенный пункт, где проживает Сергей,

· С – населенный пункт, где проходит олимпиада,

· d – стоимость проезда 1 километра на такси. 

Следующая строка содержит количество дорог m. Каждая из следующих m строк описывает дорогу – два целых числа (номера населенных пунктов, которые соединяет дорога) и действительное число – длина соответствующей дороги в километрах.

Все целые числа натуральные и не больше 100.

Выход. Выведите действительное число – сумму, на которую пришлось заплатить больше, заезжая за Сергеем или -1, если из пункта А не существует маршрута до населенного пункта, где проживает Сергей, или из пункта А не существует маршрута к месту проведения олимпиады.

Пример входа	Пример выхода
5 1 2 3 4.25 5 1 4 2.5 4 2 3 4 5 3 3 5 2 3 4 8	25.5

РЕШЕНИЕ

графы - Дейкстра

Анализ алгоритма

Во взвешенном графе при помощи алгоритма Дейкстры ищем:

· кратчайший путь dist_ab от A до B;

· кратчайший путь dist_ac от A до C;

· кратчайший путь dist_bc от B до C;

Расстояние от Ивана до места проведения олимпиады равно dist_ac.

Расстояние от Ивана до места проведения олимпиады с заездом за Сергеем равно dist_ab + dist_bc.

Ответ на задачу равен (dist_ab + dist_bc – dist_ac) * d.

Пример

Граф дорог имеет вид:

Вычисляем кратчайшие расстояния:

· кратчайший путь dist_ab от A до B равен 5.5;

· кратчайший путь dist_ac от A до C равен 7.5;

· кратчайший путь dist_bc от B до C равен 8;

Расстояние от Ивана до места проведения олимпиады равно dist_ac = 7.5.

Расстояние от Ивана до места проведения олимпиады с заездом за Сергеем равно dist_ab + dist_bc = 5.5 + 8 = 13.5.

Ответ на задачу равен

(dist_ab + dist_bc – dist_ac) * d = (5.5 + 8 – 7.5) * 4.25 = 6 * 4.25 = 25.5

Реализация алгоритма

Граф храним в весовой матрице g. Объявим массив кратчайших расстояний dist и массив вершин used, расстояние до которых уже посчитано.

#define MAX 110

double g[MAX][MAX], dist[MAX];

int used[MAX];

Функция Dijkstra возвращает длину кратчайшего пути от s до f.

double Dijkstra(int s, int f)

{

memset(used, 0, sizeof(used));

for (i = 1; i <= n; i++) dist[i] = 1e18;

dist[s] = 0;

for (i = 1; i < n; i++)

{

double min = 1e18;

int w = -1;

for (j = 1; j <= n; j++)

if (used[j] == 0 && dist[j] < min) { min = dist[j]; w = j; }

if (min == 1e18) break;

for (j = 1; j <= n; j++)

if (used[j] == 0) dist[j] = minimum(dist[j], dist[w] + g[w][j]);

used[w] = 1;

}

return dist[f];

}

Основная часть программы. Читаем входные данные.

scanf("%d %d %d %d %lf", &n, &a, &b, &c, &d);

scanf("%d", &m);

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++) g[i][j] = 1e18;

for (i = 0; i < m; i++)

{

scanf("%d %d %lf", &s, &f, &w);

g[s][f] = g[f][s] = w;

}

Вычисляем значения dist_ab, dist_bc, dist_ac.

double d1 = Dijkstra(a, b);

double d2 = Dijkstra(b, c);

double ds = Dijkstra(a, c);

Если одно из значений равно плюс бесконечности, то соответствующего пути не существует. Выводим -1.

if (d1 == 1e18 || d2 == 1e18 || ds == 1e18) printf("-1\n");

Иначе выводим ответ (dist_ab + dist_bc – dist_ac) * d.

else printf("%lf\n", (d1 + d2 - ds) * d);